#include <iostream>
#include <vector>
using namespace std;

int max_sum(vector<int> &nums)
{
        int n = nums.size();
        vector<int> dpl(n, 0);
        vector<int> dplp(n, 0);

        vector<int> dpr(n, 0);
        vector<int> dprp(n, 0);

        dpl[0] = nums[0];
        dplp[0] = 0;

        dpr[n - 1] = nums[n - 1];
        dprp[n - 1] = n - 1;

        int lmax_sum = dpl[0];
        int lpos = 0;

        int rmax_sum = dpr[n - 1];
        int rpos = n - 1;

        for(int l = 1, r = n - 2; l < n; l++, r--){
                dpl[l]= max(dpl[l - 1] + nums[l], nums[l]);
                if(dpl[l] > lmax_sum){
                        lmax_sum = dpl[l];
                        lpos = l;
                }
                dplp[l] = lpos;

                dpr[r] = max(dpr[r + 1] + nums[r], nums[r]);
                if(dpr[r] > rmax_sum){
                        rmax_sum = dpr[r];
                        rpos = r;
                }
                dprp[r] = rpos;
        }

        int ans = INT32_MIN;
        for(int i = 0; i < n - 1; i++){
                ans = max(ans, dpl[dplp[i]] + dpr[dprp[i + 1]]);
        }
        return ans;
}

int main()
{
        int t = 0;
        cin >> t;
        while(t--){
                int n = 0;
                cin >> n;
                vector<int> nums(n, 0);
                for(int i = 0; i < n; i++){
                        cin >> nums[i];
                }
                cout<<max_sum(nums)<<endl;
        }
        return 0;
}